import {
  BufferAttribute,
  BufferGeometry,
  Float32BufferAttribute,
  InstancedBufferAttribute,
  InterleavedBuffer,
  InterleavedBufferAttribute,
  TriangleFanDrawMode,
  TriangleStripDrawMode,
  TrianglesDrawMode,
  Vector3,
} from 'three'

function computeMikkTSpaceTangents(geometry, MikkTSpace, negateSign = true) {
  if (!MikkTSpace || !MikkTSpace.isReady) {
    throw new Error(
      'BufferGeometryUtils: Initialized MikkTSpace library required.',
    )
  }

  if (
    !geometry.hasAttribute('position') ||
    !geometry.hasAttribute('normal') ||
    !geometry.hasAttribute('uv')
  ) {
    throw new Error(
      'BufferGeometryUtils: Tangents require "position", "normal", and "uv" attributes.',
    )
  }

  function getAttributeArray(attribute) {
    if (attribute.normalized || attribute.isInterleavedBufferAttribute) {
      const dstArray = new Float32Array(attribute.count * attribute.itemSize)

      for (let i = 0, j = 0; i < attribute.count; i++) {
        dstArray[j++] = attribute.getX(i)
        dstArray[j++] = attribute.getY(i)

        if (attribute.itemSize > 2) {
          dstArray[j++] = attribute.getZ(i)
        }
      }

      return dstArray
    }

    if (attribute.array instanceof Float32Array) {
      return attribute.array
    }

    return new Float32Array(attribute.array)
  }

  // MikkTSpace algorithm requires non-indexed input.

  const _geometry = geometry.index ? geometry.toNonIndexed() : geometry

  // Compute vertex tangents.

  const tangents = MikkTSpace.generateTangents(
    getAttributeArray(_geometry.attributes.position),
    getAttributeArray(_geometry.attributes.normal),
    getAttributeArray(_geometry.attributes.uv),
  )

  // Texture coordinate convention of glTF differs from the apparent
  // default of the MikkTSpace library; .w component must be flipped.

  if (negateSign) {
    for (let i = 3; i < tangents.length; i += 4) {
      tangents[i] *= -1
    }
  }

  //

  _geometry.setAttribute('tangent', new BufferAttribute(tangents, 4))

  if (geometry !== _geometry) {
    geometry.copy(_geometry)
  }

  return geometry
}

/**
 * @param  {Array<BufferGeometry>} geometries
 * @param  {Boolean} useGroups
 * @return {BufferGeometry}
 */
function mergeGeometries(geometries, useGroups = false) {
  const isIndexed = geometries[0].index !== null

  const attributesUsed = new Set(Object.keys(geometries[0].attributes))
  const morphAttributesUsed = new Set(
    Object.keys(geometries[0].morphAttributes),
  )

  const attributes = {}
  const morphAttributes = {}

  const morphTargetsRelative = geometries[0].morphTargetsRelative

  const mergedGeometry = new BufferGeometry()

  let offset = 0

  for (let i = 0; i < geometries.length; ++i) {
    const geometry = geometries[i]
    let attributesCount = 0

    // ensure that all geometries are indexed, or none

    if (isIndexed !== (geometry.index !== null)) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' +
          i +
          '. All geometries must have compatible attributes; make sure index attribute exists among all geometries, or in none of them.',
      )
      return null
    }

    // gather attributes, exit early if they're different

    for (const name in geometry.attributes) {
      if (!attributesUsed.has(name)) {
        console.error(
          'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' +
            i +
            '. All geometries must have compatible attributes; make sure "' +
            name +
            '" attribute exists among all geometries, or in none of them.',
        )
        return null
      }

      if (attributes[name] === undefined) attributes[name] = []

      attributes[name].push(geometry.attributes[name])

      attributesCount++
    }

    // ensure geometries have the same number of attributes

    if (attributesCount !== attributesUsed.size) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' +
          i +
          '. Make sure all geometries have the same number of attributes.',
      )
      return null
    }

    // gather morph attributes, exit early if they're different

    if (morphTargetsRelative !== geometry.morphTargetsRelative) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' +
          i +
          '. .morphTargetsRelative must be consistent throughout all geometries.',
      )
      return null
    }

    for (const name in geometry.morphAttributes) {
      if (!morphAttributesUsed.has(name)) {
        console.error(
          'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' +
            i +
            '.  .morphAttributes must be consistent throughout all geometries.',
        )
        return null
      }

      if (morphAttributes[name] === undefined) morphAttributes[name] = []

      morphAttributes[name].push(geometry.morphAttributes[name])
    }

    if (useGroups) {
      let count

      if (isIndexed) {
        count = geometry.index.count
      } else if (geometry.attributes.position !== undefined) {
        count = geometry.attributes.position.count
      } else {
        console.error(
          'THREE.BufferGeometryUtils: .mergeGeometries() failed with geometry at index ' +
            i +
            '. The geometry must have either an index or a position attribute',
        )
        return null
      }

      mergedGeometry.addGroup(offset, count, i)

      offset += count
    }
  }

  // merge indices

  if (isIndexed) {
    let indexOffset = 0
    const mergedIndex = []

    for (let i = 0; i < geometries.length; ++i) {
      const index = geometries[i].index

      for (let j = 0; j < index.count; ++j) {
        mergedIndex.push(index.getX(j) + indexOffset)
      }

      indexOffset += geometries[i].attributes.position.count
    }

    mergedGeometry.setIndex(mergedIndex)
  }

  // merge attributes

  for (const name in attributes) {
    const mergedAttribute = mergeAttributes(attributes[name])

    if (!mergedAttribute) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeGeometries() failed while trying to merge the ' +
          name +
          ' attribute.',
      )
      return null
    }

    mergedGeometry.setAttribute(name, mergedAttribute)
  }

  // merge morph attributes

  for (const name in morphAttributes) {
    const numMorphTargets = morphAttributes[name][0].length

    if (numMorphTargets === 0) break

    mergedGeometry.morphAttributes = mergedGeometry.morphAttributes || {}
    mergedGeometry.morphAttributes[name] = []

    for (let i = 0; i < numMorphTargets; ++i) {
      const morphAttributesToMerge = []

      for (let j = 0; j < morphAttributes[name].length; ++j) {
        morphAttributesToMerge.push(morphAttributes[name][j][i])
      }

      const mergedMorphAttribute = mergeAttributes(morphAttributesToMerge)

      if (!mergedMorphAttribute) {
        console.error(
          'THREE.BufferGeometryUtils: .mergeGeometries() failed while trying to merge the ' +
            name +
            ' morphAttribute.',
        )
        return null
      }

      mergedGeometry.morphAttributes[name].push(mergedMorphAttribute)
    }
  }

  return mergedGeometry
}

/**
 * @param {Array<BufferAttribute>} attributes
 * @return {BufferAttribute}
 */
function mergeAttributes(attributes) {
  let TypedArray
  let itemSize
  let normalized
  let gpuType = -1
  let arrayLength = 0

  for (let i = 0; i < attributes.length; ++i) {
    const attribute = attributes[i]

    if (TypedArray === undefined) TypedArray = attribute.array.constructor
    if (TypedArray !== attribute.array.constructor) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.array must be of consistent array types across matching attributes.',
      )
      return null
    }

    if (itemSize === undefined) itemSize = attribute.itemSize
    if (itemSize !== attribute.itemSize) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.itemSize must be consistent across matching attributes.',
      )
      return null
    }

    if (normalized === undefined) normalized = attribute.normalized
    if (normalized !== attribute.normalized) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.normalized must be consistent across matching attributes.',
      )
      return null
    }

    if (gpuType === -1) gpuType = attribute.gpuType
    if (gpuType !== attribute.gpuType) {
      console.error(
        'THREE.BufferGeometryUtils: .mergeAttributes() failed. BufferAttribute.gpuType must be consistent across matching attributes.',
      )
      return null
    }

    arrayLength += attribute.count * itemSize
  }

  const array = new TypedArray(arrayLength)
  const result = new BufferAttribute(array, itemSize, normalized)
  let offset = 0

  for (let i = 0; i < attributes.length; ++i) {
    const attribute = attributes[i]
    if (attribute.isInterleavedBufferAttribute) {
      const tupleOffset = offset / itemSize
      for (let j = 0, l = attribute.count; j < l; j++) {
        for (let c = 0; c < itemSize; c++) {
          const value = attribute.getComponent(j, c)
          result.setComponent(j + tupleOffset, c, value)
        }
      }
    } else {
      array.set(attribute.array, offset)
    }

    offset += attribute.count * itemSize
  }

  if (gpuType !== undefined) {
    result.gpuType = gpuType
  }

  return result
}

/**
 * @param {BufferAttribute} attribute
 * @return {BufferAttribute}
 */
export function deepCloneAttribute(attribute) {
  if (
    attribute.isInstancedInterleavedBufferAttribute ||
    attribute.isInterleavedBufferAttribute
  ) {
    return deinterleaveAttribute(attribute)
  }

  if (attribute.isInstancedBufferAttribute) {
    return new InstancedBufferAttribute().copy(attribute)
  }

  return new BufferAttribute().copy(attribute)
}

/**
 * @param {Array<BufferAttribute>} attributes
 * @return {Array<InterleavedBufferAttribute>}
 */
function interleaveAttributes(attributes) {
  // Interleaves the provided attributes into an InterleavedBuffer and returns
  // a set of InterleavedBufferAttributes for each attribute
  let TypedArray
  let arrayLength = 0
  let stride = 0

  // calculate the length and type of the interleavedBuffer
  for (let i = 0, l = attributes.length; i < l; ++i) {
    const attribute = attributes[i]

    if (TypedArray === undefined) TypedArray = attribute.array.constructor
    if (TypedArray !== attribute.array.constructor) {
      console.error('AttributeBuffers of different types cannot be interleaved')
      return null
    }

    arrayLength += attribute.array.length
    stride += attribute.itemSize
  }

  // Create the set of buffer attributes
  const interleavedBuffer = new InterleavedBuffer(
    new TypedArray(arrayLength),
    stride,
  )
  let offset = 0
  const res = []
  const getters = ['getX', 'getY', 'getZ', 'getW']
  const setters = ['setX', 'setY', 'setZ', 'setW']

  for (let j = 0, l = attributes.length; j < l; j++) {
    const attribute = attributes[j]
    const itemSize = attribute.itemSize
    const count = attribute.count
    const iba = new InterleavedBufferAttribute(
      interleavedBuffer,
      itemSize,
      offset,
      attribute.normalized,
    )
    res.push(iba)

    offset += itemSize

    // Move the data for each attribute into the new interleavedBuffer
    // at the appropriate offset
    for (let c = 0; c < count; c++) {
      for (let k = 0; k < itemSize; k++) {
        iba[setters[k]](c, attribute[getters[k]](c))
      }
    }
  }

  return res
}

// returns a new, non-interleaved version of the provided attribute
export function deinterleaveAttribute(attribute) {
  const cons = attribute.data.array.constructor
  const count = attribute.count
  const itemSize = attribute.itemSize
  const normalized = attribute.normalized

  const array = new cons(count * itemSize)
  let newAttribute
  if (attribute.isInstancedInterleavedBufferAttribute) {
    newAttribute = new InstancedBufferAttribute(
      array,
      itemSize,
      normalized,
      attribute.meshPerAttribute,
    )
  } else {
    newAttribute = new BufferAttribute(array, itemSize, normalized)
  }

  for (let i = 0; i < count; i++) {
    newAttribute.setX(i, attribute.getX(i))

    if (itemSize >= 2) {
      newAttribute.setY(i, attribute.getY(i))
    }

    if (itemSize >= 3) {
      newAttribute.setZ(i, attribute.getZ(i))
    }

    if (itemSize >= 4) {
      newAttribute.setW(i, attribute.getW(i))
    }
  }

  return newAttribute
}

// deinterleaves all attributes on the geometry
export function deinterleaveGeometry(geometry) {
  const attributes = geometry.attributes
  const morphTargets = geometry.morphTargets
  const attrMap = new Map()

  for (const key in attributes) {
    const attr = attributes[key]
    if (attr.isInterleavedBufferAttribute) {
      if (!attrMap.has(attr)) {
        attrMap.set(attr, deinterleaveAttribute(attr))
      }

      attributes[key] = attrMap.get(attr)
    }
  }

  for (const key in morphTargets) {
    const attr = morphTargets[key]
    if (attr.isInterleavedBufferAttribute) {
      if (!attrMap.has(attr)) {
        attrMap.set(attr, deinterleaveAttribute(attr))
      }

      morphTargets[key] = attrMap.get(attr)
    }
  }
}

/**
 * @param {BufferGeometry} geometry
 * @return {number}
 */
function estimateBytesUsed(geometry) {
  // Return the estimated memory used by this geometry in bytes
  // Calculate using itemSize, count, and BYTES_PER_ELEMENT to account
  // for InterleavedBufferAttributes.
  let mem = 0
  for (const name in geometry.attributes) {
    const attr = geometry.getAttribute(name)
    mem += attr.count * attr.itemSize * attr.array.BYTES_PER_ELEMENT
  }

  const indices = geometry.getIndex()
  mem += indices
    ? indices.count * indices.itemSize * indices.array.BYTES_PER_ELEMENT
    : 0
  return mem
}

/**
 * @param {BufferGeometry} geometry
 * @param {number} tolerance
 * @return {BufferGeometry}
 */
function mergeVertices(geometry, tolerance = 1e-4) {
  tolerance = Math.max(tolerance, Number.EPSILON)

  // Generate an index buffer if the geometry doesn't have one, or optimize it
  // if it's already available.
  const hashToIndex = {}
  const indices = geometry.getIndex()
  const positions = geometry.getAttribute('position')
  const vertexCount = indices ? indices.count : positions.count

  // next value for triangle indices
  let nextIndex = 0

  // attributes and new attribute arrays
  const attributeNames = Object.keys(geometry.attributes)
  const tmpAttributes = {}
  const tmpMorphAttributes = {}
  const newIndices = []
  const getters = ['getX', 'getY', 'getZ', 'getW']
  const setters = ['setX', 'setY', 'setZ', 'setW']

  // Initialize the arrays, allocating space conservatively. Extra
  // space will be trimmed in the last step.
  for (let i = 0, l = attributeNames.length; i < l; i++) {
    const name = attributeNames[i]
    const attr = geometry.attributes[name]

    tmpAttributes[name] = new attr.constructor(
      new attr.array.constructor(attr.count * attr.itemSize),
      attr.itemSize,
      attr.normalized,
    )

    const morphAttributes = geometry.morphAttributes[name]
    if (morphAttributes) {
      if (!tmpMorphAttributes[name]) tmpMorphAttributes[name] = []
      morphAttributes.forEach((morphAttr, i) => {
        const array = new morphAttr.array.constructor(
          morphAttr.count * morphAttr.itemSize,
        )
        tmpMorphAttributes[name][i] = new morphAttr.constructor(
          array,
          morphAttr.itemSize,
          morphAttr.normalized,
        )
      })
    }
  }

  // convert the error tolerance to an amount of decimal places to truncate to
  const halfTolerance = tolerance * 0.5
  const exponent = Math.log10(1 / tolerance)
  const hashMultiplier = Math.pow(10, exponent)
  const hashAdditive = halfTolerance * hashMultiplier
  for (let i = 0; i < vertexCount; i++) {
    const index = indices ? indices.getX(i) : i

    // Generate a hash for the vertex attributes at the current index 'i'
    let hash = ''
    for (let j = 0, l = attributeNames.length; j < l; j++) {
      const name = attributeNames[j]
      const attribute = geometry.getAttribute(name)
      const itemSize = attribute.itemSize

      for (let k = 0; k < itemSize; k++) {
        // double tilde truncates the decimal value
        hash += `${~~(attribute[getters[k]](index) * hashMultiplier + hashAdditive)},`
      }
    }

    // Add another reference to the vertex if it's already
    // used by another index
    if (hash in hashToIndex) {
      newIndices.push(hashToIndex[hash])
    } else {
      // copy data to the new index in the temporary attributes
      for (let j = 0, l = attributeNames.length; j < l; j++) {
        const name = attributeNames[j]
        const attribute = geometry.getAttribute(name)
        const morphAttributes = geometry.morphAttributes[name]
        const itemSize = attribute.itemSize
        const newArray = tmpAttributes[name]
        const newMorphArrays = tmpMorphAttributes[name]

        for (let k = 0; k < itemSize; k++) {
          const getterFunc = getters[k]
          const setterFunc = setters[k]
          newArray[setterFunc](nextIndex, attribute[getterFunc](index))

          if (morphAttributes) {
            for (let m = 0, ml = morphAttributes.length; m < ml; m++) {
              newMorphArrays[m][setterFunc](
                nextIndex,
                morphAttributes[m][getterFunc](index),
              )
            }
          }
        }
      }

      hashToIndex[hash] = nextIndex
      newIndices.push(nextIndex)
      nextIndex++
    }
  }

  // generate result BufferGeometry
  const result = geometry.clone()
  for (const name in geometry.attributes) {
    const tmpAttribute = tmpAttributes[name]

    result.setAttribute(
      name,
      new tmpAttribute.constructor(
        tmpAttribute.array.slice(0, nextIndex * tmpAttribute.itemSize),
        tmpAttribute.itemSize,
        tmpAttribute.normalized,
      ),
    )

    if (!(name in tmpMorphAttributes)) continue

    for (let j = 0; j < tmpMorphAttributes[name].length; j++) {
      const tmpMorphAttribute = tmpMorphAttributes[name][j]

      result.morphAttributes[name][j] = new tmpMorphAttribute.constructor(
        tmpMorphAttribute.array.slice(
          0,
          nextIndex * tmpMorphAttribute.itemSize,
        ),
        tmpMorphAttribute.itemSize,
        tmpMorphAttribute.normalized,
      )
    }
  }

  // indices

  result.setIndex(newIndices)

  return result
}

/**
 * @param {BufferGeometry} geometry
 * @param {number} drawMode
 * @return {BufferGeometry}
 */
function toTrianglesDrawMode(geometry, drawMode) {
  if (drawMode === TrianglesDrawMode) {
    console.warn(
      'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Geometry already defined as triangles.',
    )
    return geometry
  }

  if (drawMode === TriangleFanDrawMode || drawMode === TriangleStripDrawMode) {
    let index = geometry.getIndex()

    // generate index if not present

    if (index === null) {
      const indices = []

      const position = geometry.getAttribute('position')

      if (position !== undefined) {
        for (let i = 0; i < position.count; i++) {
          indices.push(i)
        }

        geometry.setIndex(indices)
        index = geometry.getIndex()
      } else {
        console.error(
          'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Undefined position attribute. Processing not possible.',
        )
        return geometry
      }
    }

    //

    const numberOfTriangles = index.count - 2
    const newIndices = []

    if (drawMode === TriangleFanDrawMode) {
      // gl.TRIANGLE_FAN

      for (let i = 1; i <= numberOfTriangles; i++) {
        newIndices.push(index.getX(0))
        newIndices.push(index.getX(i))
        newIndices.push(index.getX(i + 1))
      }
    } else {
      // gl.TRIANGLE_STRIP

      for (let i = 0; i < numberOfTriangles; i++) {
        if (i % 2 === 0) {
          newIndices.push(index.getX(i))
          newIndices.push(index.getX(i + 1))
          newIndices.push(index.getX(i + 2))
        } else {
          newIndices.push(index.getX(i + 2))
          newIndices.push(index.getX(i + 1))
          newIndices.push(index.getX(i))
        }
      }
    }

    if (newIndices.length / 3 !== numberOfTriangles) {
      console.error(
        'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Unable to generate correct amount of triangles.',
      )
    }

    // build final geometry

    const newGeometry = geometry.clone()
    newGeometry.setIndex(newIndices)
    newGeometry.clearGroups()

    return newGeometry
  } else {
    console.error(
      'THREE.BufferGeometryUtils.toTrianglesDrawMode(): Unknown draw mode:',
      drawMode,
    )
    return geometry
  }
}

/**
 * Calculates the morphed attributes of a morphed/skinned BufferGeometry.
 * Helpful for Raytracing or Decals.
 * @param {Mesh | Line | Points} object An instance of Mesh, Line or Points.
 * @return {Object} An Object with original position/normal attributes and morphed ones.
 */
function computeMorphedAttributes(object) {
  const _vA = new Vector3()
  const _vB = new Vector3()
  const _vC = new Vector3()

  const _tempA = new Vector3()
  const _tempB = new Vector3()
  const _tempC = new Vector3()

  const _morphA = new Vector3()
  const _morphB = new Vector3()
  const _morphC = new Vector3()

  function _calculateMorphedAttributeData(
    object,
    attribute,
    morphAttribute,
    morphTargetsRelative,
    a,
    b,
    c,
    modifiedAttributeArray,
  ) {
    _vA.fromBufferAttribute(attribute, a)
    _vB.fromBufferAttribute(attribute, b)
    _vC.fromBufferAttribute(attribute, c)

    const morphInfluences = object.morphTargetInfluences

    if (morphAttribute && morphInfluences) {
      _morphA.set(0, 0, 0)
      _morphB.set(0, 0, 0)
      _morphC.set(0, 0, 0)

      for (let i = 0, il = morphAttribute.length; i < il; i++) {
        const influence = morphInfluences[i]
        const morph = morphAttribute[i]

        if (influence === 0) continue

        _tempA.fromBufferAttribute(morph, a)
        _tempB.fromBufferAttribute(morph, b)
        _tempC.fromBufferAttribute(morph, c)

        if (morphTargetsRelative) {
          _morphA.addScaledVector(_tempA, influence)
          _morphB.addScaledVector(_tempB, influence)
          _morphC.addScaledVector(_tempC, influence)
        } else {
          _morphA.addScaledVector(_tempA.sub(_vA), influence)
          _morphB.addScaledVector(_tempB.sub(_vB), influence)
          _morphC.addScaledVector(_tempC.sub(_vC), influence)
        }
      }

      _vA.add(_morphA)
      _vB.add(_morphB)
      _vC.add(_morphC)
    }

    if (object.isSkinnedMesh) {
      object.applyBoneTransform(a, _vA)
      object.applyBoneTransform(b, _vB)
      object.applyBoneTransform(c, _vC)
    }

    modifiedAttributeArray[a * 3 + 0] = _vA.x
    modifiedAttributeArray[a * 3 + 1] = _vA.y
    modifiedAttributeArray[a * 3 + 2] = _vA.z
    modifiedAttributeArray[b * 3 + 0] = _vB.x
    modifiedAttributeArray[b * 3 + 1] = _vB.y
    modifiedAttributeArray[b * 3 + 2] = _vB.z
    modifiedAttributeArray[c * 3 + 0] = _vC.x
    modifiedAttributeArray[c * 3 + 1] = _vC.y
    modifiedAttributeArray[c * 3 + 2] = _vC.z
  }

  const geometry = object.geometry
  const material = object.material

  let a, b, c
  const index = geometry.index
  const positionAttribute = geometry.attributes.position
  const morphPosition = geometry.morphAttributes.position
  const morphTargetsRelative = geometry.morphTargetsRelative
  const normalAttribute = geometry.attributes.normal
  const morphNormal = geometry.morphAttributes.position

  const groups = geometry.groups
  const drawRange = geometry.drawRange
  let i, j, il, jl
  let group
  let start, end

  const modifiedPosition = new Float32Array(
    positionAttribute.count * positionAttribute.itemSize,
  )
  const modifiedNormal = new Float32Array(
    normalAttribute.count * normalAttribute.itemSize,
  )

  if (index !== null) {
    // indexed buffer geometry

    if (Array.isArray(material)) {
      for (i = 0, il = groups.length; i < il; i++) {
        group = groups[i]

        start = Math.max(group.start, drawRange.start)
        end = Math.min(
          group.start + group.count,
          drawRange.start + drawRange.count,
        )

        for (j = start, jl = end; j < jl; j += 3) {
          a = index.getX(j)
          b = index.getX(j + 1)
          c = index.getX(j + 2)

          _calculateMorphedAttributeData(
            object,
            positionAttribute,
            morphPosition,
            morphTargetsRelative,
            a,
            b,
            c,
            modifiedPosition,
          )

          _calculateMorphedAttributeData(
            object,
            normalAttribute,
            morphNormal,
            morphTargetsRelative,
            a,
            b,
            c,
            modifiedNormal,
          )
        }
      }
    } else {
      start = Math.max(0, drawRange.start)
      end = Math.min(index.count, drawRange.start + drawRange.count)

      for (i = start, il = end; i < il; i += 3) {
        a = index.getX(i)
        b = index.getX(i + 1)
        c = index.getX(i + 2)

        _calculateMorphedAttributeData(
          object,
          positionAttribute,
          morphPosition,
          morphTargetsRelative,
          a,
          b,
          c,
          modifiedPosition,
        )

        _calculateMorphedAttributeData(
          object,
          normalAttribute,
          morphNormal,
          morphTargetsRelative,
          a,
          b,
          c,
          modifiedNormal,
        )
      }
    }
  } else {
    // non-indexed buffer geometry

    if (Array.isArray(material)) {
      for (i = 0, il = groups.length; i < il; i++) {
        group = groups[i]

        start = Math.max(group.start, drawRange.start)
        end = Math.min(
          group.start + group.count,
          drawRange.start + drawRange.count,
        )

        for (j = start, jl = end; j < jl; j += 3) {
          a = j
          b = j + 1
          c = j + 2

          _calculateMorphedAttributeData(
            object,
            positionAttribute,
            morphPosition,
            morphTargetsRelative,
            a,
            b,
            c,
            modifiedPosition,
          )

          _calculateMorphedAttributeData(
            object,
            normalAttribute,
            morphNormal,
            morphTargetsRelative,
            a,
            b,
            c,
            modifiedNormal,
          )
        }
      }
    } else {
      start = Math.max(0, drawRange.start)
      end = Math.min(positionAttribute.count, drawRange.start + drawRange.count)

      for (i = start, il = end; i < il; i += 3) {
        a = i
        b = i + 1
        c = i + 2

        _calculateMorphedAttributeData(
          object,
          positionAttribute,
          morphPosition,
          morphTargetsRelative,
          a,
          b,
          c,
          modifiedPosition,
        )

        _calculateMorphedAttributeData(
          object,
          normalAttribute,
          morphNormal,
          morphTargetsRelative,
          a,
          b,
          c,
          modifiedNormal,
        )
      }
    }
  }

  const morphedPositionAttribute = new Float32BufferAttribute(
    modifiedPosition,
    3,
  )
  const morphedNormalAttribute = new Float32BufferAttribute(modifiedNormal, 3)

  return {
    positionAttribute: positionAttribute,
    normalAttribute: normalAttribute,
    morphedPositionAttribute: morphedPositionAttribute,
    morphedNormalAttribute: morphedNormalAttribute,
  }
}

function mergeGroups(geometry) {
  if (geometry.groups.length === 0) {
    console.warn(
      'THREE.BufferGeometryUtils.mergeGroups(): No groups are defined. Nothing to merge.',
    )
    return geometry
  }

  let groups = geometry.groups

  // sort groups by material index

  groups = groups.sort((a, b) => {
    if (a.materialIndex !== b.materialIndex)
      return a.materialIndex - b.materialIndex

    return a.start - b.start
  })

  // create index for non-indexed geometries

  if (geometry.getIndex() === null) {
    const positionAttribute = geometry.getAttribute('position')
    const indices = []

    for (let i = 0; i < positionAttribute.count; i += 3) {
      indices.push(i, i + 1, i + 2)
    }

    geometry.setIndex(indices)
  }

  // sort index

  const index = geometry.getIndex()

  const newIndices = []

  for (let i = 0; i < groups.length; i++) {
    const group = groups[i]

    const groupStart = group.start
    const groupLength = groupStart + group.count

    for (let j = groupStart; j < groupLength; j++) {
      newIndices.push(index.getX(j))
    }
  }

  geometry.dispose() // Required to force buffer recreation
  geometry.setIndex(newIndices)

  // update groups indices

  let start = 0

  for (let i = 0; i < groups.length; i++) {
    const group = groups[i]

    group.start = start
    start += group.count
  }

  // merge groups

  let currentGroup = groups[0]

  geometry.groups = [currentGroup]

  for (let i = 1; i < groups.length; i++) {
    const group = groups[i]

    if (currentGroup.materialIndex === group.materialIndex) {
      currentGroup.count += group.count
    } else {
      currentGroup = group
      geometry.groups.push(currentGroup)
    }
  }

  return geometry
}

/**
 * Modifies the supplied geometry if it is non-indexed, otherwise creates a new,
 * non-indexed geometry. Returns the geometry with smooth normals everywhere except
 * faces that meet at an angle greater than the crease angle.
 *
 * @param {BufferGeometry} geometry
 * @param {number} [creaseAngle]
 * @return {BufferGeometry}
 */
function toCreasedNormals(
  geometry,
  creaseAngle = Math.PI / 3 /* 60 degrees */,
) {
  const creaseDot = Math.cos(creaseAngle)
  const hashMultiplier = (1 + 1e-10) * 1e2

  // reusable vectors
  const verts = [new Vector3(), new Vector3(), new Vector3()]
  const tempVec1 = new Vector3()
  const tempVec2 = new Vector3()
  const tempNorm = new Vector3()
  const tempNorm2 = new Vector3()

  // hashes a vector
  function hashVertex(v) {
    const x = ~~(v.x * hashMultiplier)
    const y = ~~(v.y * hashMultiplier)
    const z = ~~(v.z * hashMultiplier)
    return `${x},${y},${z}`
  }

  // BufferGeometry.toNonIndexed() warns if the geometry is non-indexed
  // and returns the original geometry
  const resultGeometry = geometry.index ? geometry.toNonIndexed() : geometry
  const posAttr = resultGeometry.attributes.position
  const vertexMap = {}

  // find all the normals shared by commonly located vertices
  for (let i = 0, l = posAttr.count / 3; i < l; i++) {
    const i3 = 3 * i
    const a = verts[0].fromBufferAttribute(posAttr, i3 + 0)
    const b = verts[1].fromBufferAttribute(posAttr, i3 + 1)
    const c = verts[2].fromBufferAttribute(posAttr, i3 + 2)

    tempVec1.subVectors(c, b)
    tempVec2.subVectors(a, b)

    // add the normal to the map for all vertices
    const normal = new Vector3().crossVectors(tempVec1, tempVec2).normalize()
    for (let n = 0; n < 3; n++) {
      const vert = verts[n]
      const hash = hashVertex(vert)
      if (!(hash in vertexMap)) {
        vertexMap[hash] = []
      }

      vertexMap[hash].push(normal)
    }
  }

  // average normals from all vertices that share a common location if they are within the
  // provided crease threshold
  const normalArray = new Float32Array(posAttr.count * 3)
  const normAttr = new BufferAttribute(normalArray, 3, false)
  for (let i = 0, l = posAttr.count / 3; i < l; i++) {
    // get the face normal for this vertex
    const i3 = 3 * i
    const a = verts[0].fromBufferAttribute(posAttr, i3 + 0)
    const b = verts[1].fromBufferAttribute(posAttr, i3 + 1)
    const c = verts[2].fromBufferAttribute(posAttr, i3 + 2)

    tempVec1.subVectors(c, b)
    tempVec2.subVectors(a, b)

    tempNorm.crossVectors(tempVec1, tempVec2).normalize()

    // average all normals that meet the threshold and set the normal value
    for (let n = 0; n < 3; n++) {
      const vert = verts[n]
      const hash = hashVertex(vert)
      const otherNormals = vertexMap[hash]
      tempNorm2.set(0, 0, 0)

      for (let k = 0, lk = otherNormals.length; k < lk; k++) {
        const otherNorm = otherNormals[k]
        if (tempNorm.dot(otherNorm) > creaseDot) {
          tempNorm2.add(otherNorm)
        }
      }

      tempNorm2.normalize()
      normAttr.setXYZ(i3 + n, tempNorm2.x, tempNorm2.y, tempNorm2.z)
    }
  }

  resultGeometry.setAttribute('normal', normAttr)
  return resultGeometry
}

export {
  computeMikkTSpaceTangents,
  mergeGeometries,
  mergeAttributes,
  interleaveAttributes,
  estimateBytesUsed,
  mergeVertices,
  toTrianglesDrawMode,
  computeMorphedAttributes,
  mergeGroups,
  toCreasedNormals,
}
